/*

	Raj Akula
	This program has two output files Raj's results and Ward's results
	Raj's results are when i did it even and odd matrix
	Ward's results are when i did it with 3d vertex matrix
	both results are the same but walla my method of doing it run's faster most of the time atleast 
	i did see it run faster once with Dr.Wards 3d way of doing it!!
	SVN Test
*/


//Headers
#include <omp.h>
#include <windows.h> 
#include <iostream>
#include <fstream>
#include <string>
#include <sstream>
#include <vector>
#include <map>
#include <exception>
using namespace std;

//Exception class
class IO_Exception : public runtime_error
{
public:
	IO_Exception(const string & message) : runtime_error(message) { }
};

//Reads input into vector of vectors
void readFile(const string & fileName, vector<vector<int>> & oddMatrix, vector<vector<int>> & evenMatrix)
{
    ifstream infile(fileName.c_str());
    if (!infile)
        throw IO_Exception("Could not open " + fileName);
    string line;
    int value1;
    int value2;
    int weight;

    getline(infile, line);
    istringstream tempString(line);
    int size;
    tempString >> size;
    oddMatrix.resize(size);
	evenMatrix.resize(size);

    for(unsigned int i = 0; i < oddMatrix.size(); i++)
	{
        oddMatrix[i].resize(size, 2000000000);
        
    }
	for(unsigned int i = 0; i < evenMatrix.size(); i++)
	{
		evenMatrix[i].resize(size, 2000000000);
	}

    while (getline(infile, line))
    {
        istringstream st(line);
        st >> value1;
        st >> value2;
        st >> weight;
        
        if (st.fail())
        {
            cerr << "Skipping " << line << endl;
            continue;
        }
        
        evenMatrix[value1][value2] = weight;
		oddMatrix[value1][value2] = weight;
	}
	for(unsigned int i = 0; i < evenMatrix.size(); i++)
	{
		evenMatrix[i][i] = 0;
		oddMatrix[i][i] = 0;
	}
}

//Reads input into vector of vectors
void readFile(const string & fileName, vector<vector<vector<int>>> & someMatrix)
{
    ifstream infile(fileName.c_str());
    if (!infile)
        throw IO_Exception("Could not open " + fileName);
    string line;
    int value1;
    int value2;
    int weight;

    getline(infile, line);
    istringstream tempString(line);
    int size;
    tempString >> size;
	someMatrix.resize(2);
    someMatrix[0].resize(size);
	someMatrix[1].resize(size);

    for(unsigned int i = 0; i < someMatrix[0].size(); i++)
	{
        someMatrix[0][i].resize(size, 2000000000);
        
    }
	for(unsigned int i = 0; i < someMatrix[1].size(); i++)
	{
		someMatrix[1][i].resize(size, 2000000000);
	}

    while (getline(infile, line))
    {
        istringstream st(line);
        st >> value1;
        st >> value2;
        st >> weight;
        
        if (st.fail())
        {
            cerr << "Skipping " << line << endl;
            continue;
        }
        
        someMatrix[0][value1][value2] = weight;
		someMatrix[1][value1][value2] = weight;
	}
	for(unsigned int i = 0; i < someMatrix[0].size(); i++)
	{
		someMatrix[0][i][i] = 0;
		someMatrix[0][i][i] = 0;
	}
}

//Performs the Floyd Warshal Method
vector<vector<int>> & FloydWarshall(vector<vector<int>> & oddMatrix, vector<vector<int>> & evenMatrix)
{
	int size = oddMatrix.size();
	for (unsigned int k = 1; k < size; k++)
	{	
		#pragma omp parallel for
		for(int i = 0; i < size; i++)
		{	
			for (unsigned int j = 0; j < size; j++)
			{
				if(k%2 == 0)
				{	
					int distance1;
					if((oddMatrix[i][k] == 2000000000) || (oddMatrix[k][j] == 2000000000))
					{
						distance1 = 2000000000;
					}
					else
					{
						distance1 = oddMatrix[i][k] + oddMatrix[k][j];
					}
					int distance2 = oddMatrix[i][j];
					if(distance1 < distance2)
					{
						evenMatrix[i][j] = distance1;
					}
					else
					{
						evenMatrix[i][j] = distance2;
					}
				}
				else
				{
					int distance1;
					if((evenMatrix[i][k] == 2000000000) || (evenMatrix[k][j] == 2000000000))
					{
						distance1 = 2000000000;
					}
					else
					{
						distance1 = evenMatrix[i][k] + evenMatrix[k][j];
					}
					int distance2 = evenMatrix[i][j];
					if(distance1 < distance2)
					{
						oddMatrix[i][j] = distance1;
					}
					else
					{
						oddMatrix[i][j] = distance2;
					}

				}
			}
		}
	}
	if(size%2 == 0)
		return oddMatrix;
	else
		return evenMatrix;
}

vector<vector<int>> & FloydWarshall(vector<vector<vector<int>>> & someMatrix)
{
	int size = someMatrix[0].size();
	for (unsigned int k = 1; k < size; k++)
	{	
		#pragma omp parallel for
		for(int i = 0; i < size; i++)
		{	
			for (unsigned int j = 0; j < size; j++)
			{
				if(k%2 == 0)
				{	
					int distance1;
					if((someMatrix[0][i][k] == 2000000000) || (someMatrix[0][k][j] == 2000000000))
					{
						distance1 = 2000000000;
					}
					else
					{
						distance1 = someMatrix[0][i][k] + someMatrix[0][k][j];
					}
					int distance2 = someMatrix[0][i][j];
					if(distance1 < distance2)
					{
						someMatrix[1][i][j] = distance1;
					}
					else
					{
						someMatrix[1][i][j] = distance2;
					}
				}
				else
				{
					int distance1;
					if((someMatrix[1][i][k] == 2000000000) || (someMatrix[1][k][j] == 2000000000))
					{
						distance1 = 2000000000;
					}
					else
					{
						distance1 = someMatrix[1][i][k] + someMatrix[1][k][j];
					}
					int distance2 = someMatrix[1][i][j];
					if(distance1 < distance2)
					{
						someMatrix[0][i][j] = distance1;
					}
					else
					{
						someMatrix[0][i][j] = distance2;
					}

				}
			}
		}
	}
	if(size%2 == 0)
		return someMatrix[0];
	else
		return someMatrix[1];
}

//Print the matrix
void printMatrix(vector<vector<int>> & answerMatrix , int n)
{
	
	ofstream fp_out; // open a file 
	if (n==0)
		fp_out.open("Raj_Results.txt", ios::out); // specify where to output
	else if(n==1)
		fp_out.open("Ward_Results.txt", ios::out);
	fp_out << "\t"; // for formatting

	//Loop for printing number of nodes and print te numbers for formating 
	for( unsigned int i = 0; i < answerMatrix.size(); i++)
	{
		fp_out << i << "\t";
	}
	fp_out << endl;
	for(unsigned int i = 0; i < answerMatrix.size(); i++)
	{
		fp_out << i << "\t";
		for(unsigned int j = 0; j < answerMatrix.size(); j++)
		{
			if(i == j)
				fp_out << " ";
			else
				fp_out << answerMatrix[i][j];
			fp_out << "\t";
		}
		fp_out << "\n";
	}
	fp_out.close();

}

//Main Method
void main()
{
	DWORD startTime = GetTickCount(); //Start time to count how long it takes
	
	//Two vectors for k values and one for answer
	vector<vector<int>> oddMatrix;
	vector<vector<int>> evenMatrix;
	vector<vector<int>> answerMatrix;
	

	readFile("Edges.txt", oddMatrix, evenMatrix); // Reading from file putting it into matrixes
	answerMatrix = FloydWarshall(oddMatrix, evenMatrix); // Performs algorithem and places it in answer Matrix
	printMatrix(answerMatrix, 0); // Prints matrix
	DWORD totalTime = GetTickCount() - startTime; //Subtracting it from end time
	cout << "Run time for my way= " << totalTime << " milliseconds" << endl; //Displaying it in file

	startTime = GetTickCount();
	vector<vector<vector<int>>> someMatrix;
	readFile("Edges.txt", someMatrix);
	answerMatrix = FloydWarshall(someMatrix);
	printMatrix(answerMatrix, 1);
	totalTime = GetTickCount() - startTime;
	cout << "Run time for Dr. Ward's way= "  << totalTime << " milliseconds" << endl;

	system("PAUSE");
	return;
}